home *** CD-ROM | disk | FTP | other *** search
/ Skunkware 5 / Skunkware 5.iso / src / X11 / wais / ir / hash.h < prev    next >
C/C++ Source or Header  |  1995-05-09  |  4KB  |  107 lines
  1. /* hash table routines.  not very general.
  2.  * -brewster
  3.  */
  4.  
  5. #ifndef HASH_H
  6. #define HASH_H
  7.  
  8.  
  9. #define DEFAULT_NUMBER_OF_BUCKETS 65536L
  10. #define DEFAULT_NUMBER_OF_ELEMENTS 131072L
  11.  
  12. #define MAX_KEY_SIZE 20 /* this is the string length, so add 1 */
  13.  
  14. typedef struct hash_entry{
  15.   char key[MAX_KEY_SIZE + 1];    /* the key.  Must be first */
  16.   long next;    /* index of the next entry in the contents */
  17.  
  18.  
  19.   /* This part is usage dependent.  Sucks that it is hard coded. (this 
  20.    * was done for efficiency. C sucks.)
  21.    * however, this can be made to be somewhat flexible, by pulling this out
  22.    * into a different .h file, and redefining the structure for different 
  23.    * purposes.  This can be done in the same application since all the 
  24.    * hashtable code cares about is the key and next values.
  25.    * (actually, not quite, take out array refs to contents in hash.c
  26.    *  and replace by explicit multiplies and it will work).
  27.    */
  28.   
  29.   long number_of_occurances;    /* total for the whole db */
  30.   unsigned char* memory_ptr;        /* what will go into the next block */
  31.   unsigned char* current_memory_ptr;    /* the fill ptr into memory_ptr */
  32.   long memory_size;        /* the size of memory_ptr */
  33.   long current_doc_id;        /* the last document-id in memory_ptr
  34.                  * this will change a page pointer eventually
  35.                  */
  36. } hash_entry;
  37.  
  38. typedef struct hashtable{
  39.   long number_of_buckets;    /* number of buckets */
  40.   long buckets_mask;        /* a mask for fast bitwise and'ing */
  41.   long element_size;        /* sizeof the element to be stored 
  42.                    (including th hash_entry_header) */
  43.   long number_of_elements;    /* total number of elements hashed */
  44.   long max_number_of_elements;    /* size of the contents buffer in elements */
  45.  
  46.   long *buckets;        /* array of longs, each an index into contents
  47.                  * -1 is an empty entry. */
  48.   hash_entry* contents;        /* pointer to hashtable memory */
  49.  
  50. } hashtable;
  51.  
  52.  
  53. #ifdef __cplusplus
  54. /* declare these as C style functions */
  55. extern "C"
  56.     {
  57. #endif /* def __cplusplus */
  58.  
  59.  
  60. /* number_of_buckets must be a power of 2, 
  61.       if -1 then it defaults to DEFAULT_NUMBER_OF_BUCKETS.
  62.    number_of_elements is the number of expected elements that will be hashed.
  63.    element_size must be the sizeof the element to be put in the hashtable 
  64.        (not including hash_entry_header).
  65.    returns NULL if an error
  66.  */
  67. hashtable *make_hashtable _AP ((long number_of_buckets, 
  68.                  long number_of_elements,
  69.                  long element_size));
  70.  
  71. /* returns a pointer to the element stored or NULL if none. */
  72. hash_entry *get_hash _AP ((char *key, hashtable *htable));
  73.  
  74. /* puts a copy of the element into the hashtable.
  75.    Returns a pointer to the new element.
  76.  
  77.    This does not check to see that the key has not already been added. */
  78. hash_entry *put_hash _AP ((char *key, hashtable *htable, hash_entry *element));
  79.  
  80. /* not implemented yet 
  81. boolean rem_hash _AP ((char *key, hashtable *htable));
  82.  */
  83.  
  84. /* removes contents without freeing memory.
  85.    returns true if successful, false otherwise */
  86. boolean clr_hashtable _AP ((hashtable *htable));
  87.  
  88. /* removes contents and free's memory for the hastable.   
  89.    returns true if successful, false otherwise */
  90. boolean free_hashtable _AP ((hashtable *htable));
  91.  
  92. long hashtable_count _AP ((hashtable *htable));
  93.  
  94. /* sorts the contents of elements of the hastable.
  95.    this destroys the hashtable */
  96. boolean sort_hashtable _AP ((hashtable *htable));
  97.  
  98. void analyze_hashtable_distribution _AP ((hashtable * htable));
  99. void print_hashtable _AP ((hashtable *htable));
  100.  
  101.  
  102. #ifdef __cplusplus
  103.     }
  104. #endif /* def __cplusplus */
  105.  
  106. #endif /* nded HASH_H */
  107.